﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode
{
    /// <summary>
    /// 最大子序和
    /// </summary>
    public class _53MaximumSubarray :IRun
    {
        public void Run()
        {
          int _Result =  maxSubArray(new int[] { -2, 1, -3, 4, -1, 2, 1, -8, 4 });
        }
        public int maxSubArray(int[] nums)
        {
            int res = nums[0];
            int sum = 0;

            foreach (var num in nums)
            {
                if (sum > 0)
                    sum += num;
                else
                    sum = num;

                if (sum > res)
                    res = sum;
            }
            return res;
        }
    }
}
